#include "stdio.h"

typedef char VerTexType;
typedef int EdgeType;
#define MAXVEX 9
#define INFINITY 65535

typedef struct VerTex{
    VerTexType vex[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numNodes, numEdges;
}MGraph;

void MiniSpanTree_Prim(MGraph G) {
    int min, i, j, k;
    // 保存相关顶点间边的权值点下标
    int adjvex[MAXVEX];
    // 保存相关顶点边的权值
    int lowcost[MAXVEX];
    // 此处初始化权值为0，即从v0开始
    lowcost[0] = 0;
    // v0顶点下标为0
    adjvex[0] = 0;

    //循环除下标0之外的所有顶点，即v1,v2...
    for(i = 1; i < G.numNodes; i++) {
        // 所有与v0相关的边的权值存入数组
        lowcost[i] = G.arc[0][i];
        // 初始化为全都是v0的下标
        adjvex[i] = 0;
    }
    // 最小生成树操作
    for (i = 1; i < G.numNodes; i++) {
        // 初始化最小权值为65535
        min = INFINITY;
        // 顶点下标循环变量
        j = 1;
        // 存储最小权值的顶点下标
        k = 0;
        // 循环全部顶点
        while (j < G.numNodes) {
            // 权值不为0且权值小于min，则当前的就是最小权值，赋给min（类似寻找最小值操作）
            if(lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                // 存储最小权值的顶点下标
                k = j;
            }
            j++;
        }
        // 打印当前顶点边中权值最小的边
        printf("(%d,%d)\n", adjvex[k], k);
        // 将当前顶点的权值更改为0，表示此顶点已加入最小生成树，该顶点的任务完成
        lowcost[k] = 0;
        // 循环所有顶点
        for (j = 1; j < G.numNodes; j++) {
            // 若下标为k的顶点各边权值小于此前这些未被加入生成树的顶点的权值
            if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
                // 将较小的权值存入lowcost对应的下标位置
                lowcost[j] = G.arc[k][j];
                // 将下标为k的顶点存入adjvex
                adjvex[j] = k;
            }
        }
    }
}
